import random
import time

class SortAlgrithm:
    def bubble(self, array):
        length = len(array)

        # 冒泡排序
        # 第一级遍历
        for index in range(length):
            # 第二级遍历
            for j in range(1, length - index):
                if array[j - 1] > array[j]:
                    # 交换两者数据，这里没用temp是因为python 特性元组。
                    array[j - 1], array[j] = array[j], array[j - 1]

    def partition(self, arr, low, high):
        i = (low - 1)  # 最小元素索引
        pivot = arr[high]

        for j in range(low, high):

            # 当前元素小于或等于 pivot
            if arr[j] <= pivot:
                i = i + 1
                arr[i], arr[j] = arr[j], arr[i]

        arr[i + 1], arr[high] = arr[high], arr[i + 1]
        return (i + 1)

    # arr[] --> 排序数组
    # low  --> 起始索引
    # high  --> 结束索引

    # 快速排序函数
    def quickSort(self, arr, low, high):
        if low < high:
            pi = self.partition(arr, low, high)
            self.quickSort(arr, low, pi - 1)
            self.quickSort(arr, pi + 1, high)

if __name__ == "__main__":
    s = SortAlgrithm()
    array = []
    for i in range(10000):
        array.append(random.randint(1, 100000))
    a = array[:]
    b = array[:]
    bubble_s = time.time()
    s.bubble(a)
    bubble_e = time.time()
    bubble_t = bubble_e-bubble_s

    q_s =time.time()
    s.quickSort(b,0,9999)
    q_e = time.time()
    q_t = q_e-q_s
    print("冒泡排序的时间：", bubble_t)
    print("快速排序的时间：", q_t)